1. Field of the Invention
The invention relates to numerical methods for simulating semiconductor fabrication processes, devices and circuits, and more particularly to a modification of the Newton Method for improved convergence behavior in such applications.
2. Description of Related Art
Numerical modeling and simulation has become an indispensable tool for the optimal design of semiconductor devices. As the dimensions of semiconductor devices continue to decrease, numerical simulation plays an important role in helping transistor designers develop strategies to overcome the design limits. Numerical modeling is used extensively also for simulating fabrication processes, such as the diffusion of dopants in a substrate. In digital and analog circuit design and analysis, numerical modeling of circuit simulations is used to assist in circuit verification.
Modeling of problems in these fields often requires finding solutions (roots) to problems of the form F(X)=0, where F is a nonlinear function and X∈m. In most cases, this is a multidimensional problem (m>1), in which case F is a system of m nonlinear functions
      F    ⁡          (      X      )        =      [                                                      F              1                        ⁡                          (                                                x                  1                                ,                …                ⁢                                                                  ,                                  x                  m                                            )                                                            …                                                                F              m                        ⁡                          (                                                x                  1                                ,                …                ⁢                                                                  ,                                  x                  m                                            )                                            ]  in m variablesX=(x1, x2, . . . , xm).Only rarely can solutions to these problems be found in closed form; usually they must be calculated using numerical methods. As used herein, unless the context indicates otherwise, lower case letters represent scalars whereas upper case letters represent matrices, vectors or vectors of functions. Lower case letters either are scalar analogs of the matrices or vectors represented by the corresponding upper case letters, or are scalar elements in the matrices or vectors represented by the corresponding upper case letters.
The Newton Method is one well-known iterative numerical method for solving problems of this form, given an initial guess X0. The method can be derived in the 1-dimensional case by instead finding a simplifying approximation of the function F(X), and finding a root of that approximation. If the approximation was good enough, then the root of the approximation will be a reasonable approximation of the root X* of F(X). In the Newton Method, the approximation is usually taken as the straight line tangent to F(X) at an initial approximation X0 of the root X*. If X0 is close enough to X*, then the root of the straight line, X1, should be closer still to X*. A new straight line approximation of F(X) is then constructed as the tangent at X1, and the root of the new approximation is then found, and so on until the roots found for successive approximations converge to a desired precision.
The Newton Method can be written as the fixed point iteration X=G(X) with G(X)=X−F(X)/F′(X). This gives the iteration schemeX1, X2, X3, . . .defined byXn+1=G(Xn), for n=1, 2, 3, . . . , with X0 given.The iteration therefore is defined byXn+1=Xn−F(Xn)/F′(Xn).Returning to the m-dimensional case, the Newton method reads as follows:Xn+1=Xn−J−1(Xn)F(Xn), n=0, 1, . . . , with X0 given,where the m by m matrix
            J      ⁡              (        X        )              ≡                  F        ′            ⁡              (        X        )              =      [                                                      ∂                              F                1                                                    ∂                              x                1                                                              ⋯                                                    ∂                              F                1                                                    ∂                              x                m                                                                                                                          ⋯                                                                                                                ∂                              F                m                                                    ∂                              x                1                                                              ⋯                                                    ∂                              F                m                                                    ∂                              x                m                                                          ]  is sometimes called the Jacobian of F at point X. If this sequence converges then the limit is a solution of X=G(X) and therefore also a solution of F(X)=0.
Assuming a close enough initial guess, in many cases convergence of the Newton Method is quadratic. The Newton Method is therefore an extremely valuable tool. But in some cases convergence is only linear or slower, and in some cases the method will never converge. In the situation where the Jacobian F′(Xn) is not positive definite, the conventional Newton iteration from Xn may not be in a descent direction. If the Jacobian is singular, then the iteration might not be computable at all.
Several modifications to Newton's Method to improve convergence behavior are known. In one known modification, a scaled identity matrix is added to the Jacobian to ensure that it is positive definite. A well-known member of this class of methods is the Levenberg-Marquardt method, in which a scalar multiple of the identity matrix is added to the symmetrized Jacobian,(JTJ+μI)−1JTF(Xn),thus shifting all the eigenvalues equally. This modification is computationally inexpensive for problems of relatively small size, but also sometimes fails to converge, for example where the addition of the identity matrix multiple is taken too small and in computer arithmetic still produces zeros on the diagonal.
A more sophisticated member of this class of methods is known as modified Cholesky factorization, where the shift in the Jacobian is calculated during factorization in such a way as to ensure that the resulting iteration step will lead to a decrease in the function value. See Stephen J. Wright, “Modified Cholesky factorizations in interior-point algorithms for linear programming,” SIAM Journal on Optimization 9 (1999), pp. 1159-1191. This method may produce convergence in more situations, but is computationally much more expensive than either the basic Newton Method or the Levenberg-Marquardt method. In real world modeling of semiconductor devices, fabrication processes and analog circuits, the number of variables involved and the multiplicity of nodes at which the roots must be found usually render it prohibitive to incur the additional computational expense of the Levenberg-Marquardt or the modified Cholesky factorization methods.
Other modifications to the Newton Method are also known, but in general either they do not produce convergence in a sufficient number of cases, or where they do, they are too expensive computationally for use in real world modeling of semiconductor devices, fabrication processes and analog circuits. Accordingly, there is a need for an improved modification to the Newton Method which converges in difficult situations, and which does so without significant additional computational expense.